package com.isaiah.graph.adjacencylist;

import java.net.Inet4Address;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Title:  图的广度搜索
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/6/613:31
 */
public class BreadthFirstSearch {
    /** 索引代表顶点， 值表示当前顶点是否已被访问过 */
    private boolean[] isVisited;
    /** 记录有多少个顶点与s顶点相通 */
    private int count;
    /** 用来存储等待遍历的邻接表的点 */
    private Queue<Integer> waitSearch;

    /**
     * 构造广度优先搜索对象，使用广度优先搜索找到G图中s顶点所有相邻顶点
     * @param G
     * @param s
     */
    public BreadthFirstSearch(Graph G, int s) {
        this.isVisited = new boolean[G.V()];
        this.count = 0;
        this.waitSearch = new LinkedList<>();
        bfs(G, s);
    }

    /**
     * 使用广度优先遍历找出G图中v顶点的所有相邻顶点
     * @param G
     * @param v
     */
    private void bfs(Graph G, int v) {
        // 将当前顶点v标记为已访问
        isVisited[v] = true;
        // 让顶点v进入队列，等待遍历
        waitSearch.add(v);
        //    循环遍历，如果队列不为空，则从队列中弹出一个等待遍历的顶点进行遍历
        while (!waitSearch.isEmpty()){
            Integer wait = waitSearch.poll();
            // 遍历wait顶点的邻接表
            for (Integer w : G.addj(wait)){
                if (!isVisited[w]){
                    bfs(G, w);
                }
            }
        }
        // 让相通的顶点数加1
        count++;
    }

    /**
     * 判断w顶点与s顶点是否相通
     * @param w
     * @return
     */
    public boolean isVisited(int w){
        return isVisited[w];
    }

    /**
     * 获取与顶点s相通的所有顶点的总数
     * @return
     */
    public int count(){
        return count;
    }
}
